/**
 * 
 */
package com.hww.sort.impl;

import com.hww.sort.ISortNumber;

/**
 * @author:Huangwenwei
 * @date:2014-6-18
 * @time:下午5:46:56
 */
public class QuickSort implements ISortNumber {

	public QuickSort() {
	}

	@Override
	public int[] sortASC(int[] intArray) {
		if (intArray == null)
			return null;
		int[] srcData = (int[]) intArray.clone();
		return this.quickSort(srcData, 0, srcData.length - 1);
	}

	/**
	 * 采用分治遞歸方法實現快速排序
	 * 
	 * @Time:下午5:56:20
	 * @Data:2014-6-18
	 * @Auto:mr.huangwenwei@gmail.com
	 * @param srcData帶排序的數組
	 * @param i起始下標
	 * @param j終止下標
	 * @return 排序好的數組
	 * @Return:int[]
	 */
	private int[] quickSort(int[] srcData, int i, int j) {
		if (i < j) {
			int pos = partition(srcData, i, j);
			quickSort(srcData, i, pos-1);
			quickSort(srcData, pos + 1, j);
		}
		return srcData;
	}

	/**
	 * 尋找數組分治點
	 * 根據數組的第一個數分治，把數組第一個數大的往後排，把數組第一個數小的往前排
	 * @Time:下午6:02:33
	 * @Data:2014-6-18
	 * @Auto:mr.huangwenwei@gmail.com
	 * @param srcData帶排序的數組
	 * @param i起始下標
	 * @param j終止下標
	 * @Return:int 傳入數組的第一个数的最終下標
	 */
	private int partition(int[] srcData, int first, int last) {
		int temp = srcData[first];
		int pos = first;
		for (int i = first + 1; i <= last; i++) {
			if (srcData[i] < temp) {
				pos++;
				swap(srcData, pos, i);
			}
		}
		swap(srcData, first, pos);
		return pos;
	}

	/**
	 * 交換數組中下標爲i,j的值
	 * 
	 * @Time:下午6:58:10
	 * @Data:2014-6-18
	 * @Auto:mr.huangwenwei@gmail.com
	 * @param srcData
	 * @param pos
	 * @param i
	 * @Return:void
	 */
	private void swap(int[] srcData, int i, int j) {
		int temp = srcData[i];
		srcData[i] = srcData[j];
		srcData[j] = temp;
	}
}
